package com.leetcode.partition9;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/12/13 17:19
 */
@SuppressWarnings("all")
public class LC815公交路线 {

    public static void main(String[] args) {
        int[][] routes = {{1, 2, 7}, {3, 6, 7}};
        int source = 1, target = 6;
//        int[][] routes = {{7, 12}, {4, 5, 15}, {6}, {15, 19}, {9, 12, 13}};
//        int source = 15, target = 12;
        System.out.println(numBusesToDestination(routes, source, target));
    }

    public static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        //并查集预处理不能到达的情况
        int[] parent = new int[(int) (1e5 + 10)];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                union(parent, routes[i][0], routes[i][j]);
            }
        }
        if (find(parent, source) != find(parent, target)) return -1;
        return bfs(routes, source, target);
    }

    private static int find(int[] parent, int x) {
        if (x != parent[x]) parent[x] = find(parent, parent[x]);
        return parent[x];
    }

    private static void union(int[] parent, int x, int y) {
        int a = find(parent, x), b = find(parent, y);
        if (a != b) parent[b] = a;
    }

    private static int bfs(int[][] routes, int source, int target) {
        Map<Integer, Set<Integer>> lineToBus = new HashMap<>();
        LinkedList<Integer> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        Map<Integer, Integer> step1 = new HashMap<>(), step2 = new HashMap<>();
        //将每个路线看做一个点，当不同路线之间存在公交车站，则为其增加一条权为1的边
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                Set<Integer> busSet = lineToBus.getOrDefault(routes[i][j], new HashSet<>());
                busSet.add(i);
                lineToBus.put(routes[i][j], busSet);
                if (routes[i][j] == source) {
                    queue1.addLast(i);
                    step1.put(i, 1);
                }
                if (routes[i][j] == target) {
                    queue2.addLast(i);
                    step2.put(i, 1);
                }
            }
        }
        //如果起点线路和终点与交集，直接返回
        Set<Integer> tot = new HashSet<>();
        tot.addAll(lineToBus.get(source));
        tot.retainAll(lineToBus.get(target));
        if (!tot.isEmpty()) return 1;

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int ans = queue1.size() < queue2.size() ? search(lineToBus, routes, queue2, step2, step1) :
                    search(lineToBus, routes, queue1, step1, step2);
            if (ans != -1) return ans;
        }
        return -1;
    }

    private static int search(Map<Integer, Set<Integer>> lineToBus, int[][] routes, LinkedList<Integer> queue, Map<Integer,
            Integer> cur, Map<Integer, Integer> other) {
        //取出当前路线点，并搜索它能到达其它地方的路线
        int bus = queue.pollFirst(), step = cur.get(bus);
        for (int line : routes[bus]) {
            //得到当前路线有哪些公交车会走
            Set<Integer> busSet = lineToBus.get(line);
            if (busSet == null) continue;
            for (int nextBus : busSet) {
                if (cur.containsKey(nextBus)) continue;
                if (other.containsKey(nextBus)) return step + other.get(nextBus);
                cur.put(nextBus, step + 1);
                queue.addLast(nextBus);
            }
        }
        return -1;
    }
}
